package pers.vic.basics.leetcode;

import javafx.concurrent.Worker;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @description: 51. N 皇后 {@literal https://leetcode-cn.com/problems/n-queens/} 回溯
 * @author Vic.xu
 * @date: 2020/12/11 0011 17:21
 */
public class J0051_H_SolveNQueens {

    /*
    n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
    皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
    每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     */

    /**
     * 这是一个回溯算法的问题
     */
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        dfs(res, new boolean[n][n], 0, 0, n, new HashSet<Integer>(), new HashSet<Integer>(),new HashSet<Integer>(),new HashSet<Integer>() );
        return res;
    }

    /**
     * 回溯算法放皇后
     * @param res 结果集
     * @param temp 当前解法
     * @param row 放到了哪一行
     * @param column 放到了哪一列
     * @param n n皇后
     * @param rowPuted 当前解法的已放皇后的行
     * @param columnPuted 当前解法的已放皇后的列
     * @param rightObliquePuted 当前解法的已放皇后的右斜线
     * @param leftObliquePuted 当前解法的已放皇后的左斜线
     */
    public static void dfs(List<List<String>> res, boolean[][] temp, int row, int column, int n, Set<Integer> rowPuted, Set<Integer> columnPuted, Set<Integer> rightObliquePuted, Set<Integer> leftObliquePuted) {
        if (row == n) {
            List<String> solve = buildResult(temp);
            res.add(solve);
            return;
        }
        for (int i = 0; i < n; i++) {
            //检测当前行 列 右斜线 左斜线 是否可以放皇后
            boolean canPut =
                    !rowPuted.contains(row)
                            && !columnPuted.contains(i)
                            && !rightObliquePuted.contains(row - i)
                            && !leftObliquePuted.contains(row + i);
            if (canPut) {
                temp[row][i] = true;
                rowPuted.add(row);
                columnPuted.add(i);
                rightObliquePuted.add(row - i);
                leftObliquePuted.add(row + i);
                dfs(res, temp, row + 1, 0, n, rowPuted, columnPuted, rightObliquePuted, leftObliquePuted);
                //减枝
                temp[row][i] = false;
                rowPuted.remove(row);
                columnPuted.remove(i);
                rightObliquePuted.remove(row - i);
                leftObliquePuted.remove(row + i);
            }
        }
    }

    private static List<String> buildResult(boolean[][] temp) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < temp.length; i++) {
            StringBuilder sb = new StringBuilder();
            boolean[] tem = temp[i];
            for (int j = 0; j < tem.length; j++) {
                if (tem[j]) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            res.add(sb.toString());
        }
        return res;
    }




    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(8);
        System.out.println(lists.size());
        for (List<String> list : lists) {
            list.forEach(System.out::println);
            System.out.println();
        }

    }

}
